Today’s Agenda

  • Motivation
  • Hausmann’s curious question
  • Latschev’s remarkable (but qualitative!) answer
  • Finite reconstruction problem
  • Quantitative Latschev’s theorem
    • abstract manifolds
    • Euclidean submanifolds
  • Extension to CAT(κ)\mathrm{CAT}(\kappa) Spaces
  • Questions

The Vietoris–Rips Complexes

  • a metric space (X,dX)(X,d_X)

  • a scale β>0\beta>0

  • ℛβ(X)\mathcal{R}_\beta(X) is an abstract simplicial complex

    • XX is the vertex set
    • each subset A⊂XA\subset X of (k+1)(k+1) points with diameter at most β\beta is a kk-simplex.

Hausmann’s Theorem

Hausmann (1995)

For any closed Riemannian manifold MM and 0<β<ρ(M)0<\beta<\rho(M), the Vietoris–Rips complex ℛβ(M)\mathcal{R}_\beta(M) is homotopy equivalent to MM.

  • Convexity Radius ρ(M)\rho(M) is the largest (sup) radius so that geodesic balls are convex.
    • ρ(S1)=π2\rho(S^1)=\frac{\pi}{2}
    • ρ(M)>0\rho(M)>0 for a compact manifold
  • Hausmann constructed a homotopy equivalence T:ℛβ(M)→MT:\mathcal{R}_{\beta}(M)\to M
  • Since MM has finitely generated homology, so does ℛβ(M)\mathcal{R}_{\beta}(M)
  • vertex set is the entire manifold MM!

Finite Reconstruction Problem

Hausmann’s Curious Question

What about the Vietoris–Rips complex of a finite, dense subset S⊂MS\subset M?

  • Manifold reconstruction from a dense sample
  • More generally, a metric space (S,dS)(S,d_S) close to MM in the Gromov-Hausdorff distance.

Gromov–Hausdorff Distance:

  • similarity measure between abstract metric spaces (X,dX)(X,d_X) and (Y,dY)(Y,d_Y)
  • Definition: dGH(X,Y)=infdHZ(f(X),g(Y))d_{GH(X,Y)}=\inf d_H^Z(f(X),g(Y))
    • inf over metric spaces (Z,dZ)(Z,d_Z) and isometries f:X→Zf:X\to Z, g:Y→Zg:Y\to Z

Latschev’s Remarkable Solution

Latschev (2001)

Every closed Riemannian manifold MM has an ϵ0>0\epsilon_0>0 such that for any 0<β≤ϵ00<\beta\leq\epsilon_0 there exists some δ>0\delta>0 so that for any sample SS: dGH(S,M)≤δ⟹ℛβ(S)≃M. d_{GH}(S,M)\leq\delta\implies \mathcal R_\beta(S)\simeq M.

  • the threshold ϵ0=ϵ0(M)\epsilon_0=\epsilon_0(M) depends solely on the geometry of MM. But the theorem did not say how!

  • δ=δ(β)\delta=\delta(\beta) is a function (a fraction in practice) of β\beta.

  • The result is qualitative

    • it’s unavoidable (uses Lebesgue’s number lemma)

  • Nonetheless, the result provides a promising answer to Hausmann’s question, and more!

Quantitative Latschev’s Theorem

Metric Graph Reconstruction (Majhi 2023b)

Let (G,dG)(G,d_G) be a compact, path-connected metric graph, (S,dS)(S,d_S) a metric space, and β>0\beta>0 a number such that 3dGH(G,S)<β<34ρ(G).3d_{GH}(G,S)<\beta<\frac{3}{4}\rho(G). Then, ℛβ(S)≃G\mathcal R_\beta(S)\simeq G.

  • The result is quantitative

    • ϵ0=34ρ(G)\epsilon_0=\frac{3}{4}\rho(G)

    • δ=13β\delta=\frac{1}{3}\beta

  • The constants are not optimal!

    • Optimal ϵ0=23ρ(G)\epsilon_0=\frac{2}{3}\rho(G).

Quantitative Latschev’s Theorem

Riemannian Manifold Reconstruction (Majhi 2023a)

Let MM be a closed, connected Riemannian manifold. Let (S,dS)(S,d_S) be a compact metric space and β>0\beta>0 a number such that 1ξdGH(M,S)<β<11+2ξmin{ρ(M),π4κ} \frac{1}{\xi}d_{GH}(M,S)<\beta<\frac{1}{1+2\xi}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\} for some 0<ξ≤1/140<\xi\leq1/14. Then, ℛβ(S)≃M\mathcal R_\beta(S)\simeq M.

  • κ\kappa is an upper bound on the sectional curvatures of MM

  • For ξ=114\xi=\frac{1}{14}:

    • ϵ0=78min{ρ(M),π4κ}\epsilon_0=\frac{7}{8}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\}

    • δ=β14\delta=\frac{\beta}{14}

Quantitative Latschev’s Theorem

Euclidean Submanifold Reconstruction (Majhi 2023a)

Let M⊂ℝNM\subset\mathbb R^N be a closed, connected submanifold. Let S⊂ℝNS\subset\mathbb R^N be a compact subset and β>0\beta>0 a number such that 1ξdH(M,S)<β<3(1+2ξ)(1−14ξ)8(1−2ξ)2τ(M) \frac{1}{\xi}d_{H}(M,S)<\beta<\frac{3(1+2\xi)(1-14\xi)}{8(1-2\xi)^2}\tau(M) for some 0<ξ<1/140<\xi<1/14. Then, ℛβ(S)≃M\mathcal R_\beta(S)\simeq M.

  • τ(M)\tau(M) is the reach of MM

  • For ξ=128\xi=\frac{1}{28}:

    • ϵ0=3151352τ(M)\epsilon_0=\frac{315}{1352}\tau(M)

    • δ=β28\delta=\frac{\beta}{28}

Beyond Manifolds

Define CAT spaces

Lastchev’s Theorem for Abstract CAT Spaces

Lastchev’s Theorem for Euclidean CAT Spaces

Discussions

References

Chazal, Frédéric, Ruqi Huang, and Jian Sun. 2015. “Gromov–Hausdorff Approximation of Filamentary Structures Using Reeb-Type Graphs.” Discrete & Computational Geometry 53 (3): 621–49. https://doi.org/10.1007/s00454-015-9674-1.
Ge, Xiaoyin, Issam Safa, Mikhail Belkin, and Yusu Wang. 2011. “Data Skeletonization via Reeb Graphs.” In Advances in Neural Information Processing Systems, edited by J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger. Vol. 24. Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2011/file/3a0772443a0739141292a5429b952fe6-Paper.pdf.
Hausmann, Jean-Claude. 1995. “On the Vietoris-Rips Complexes and a Cohomology Theory for Metric Spaces.” In Prospects in Topology (AM-138), 175–88. Princeton University Press.
Komendarczyk, Rafal, Sushovan Majhi, and Will Tran. 2024. “Topological Stability and Latschev-Type Reconstruction Theorems for CAT(𝛋)\boldsymbol{\mathrm{CAT}(κ)} Spaces.”
Latschev, J. 2001. “Vietoris-Rips Complexes of Metric Spaces Near a Closed Riemannian Manifold.” Archiv Der Mathematik 77 (6): 522–28. https://doi.org/10.1007/PL00000526.
Majhi, Sushovan. 2023a. “Demystifying Latschev’s Theorem: Manifold Reconstruction from Noisy Data.”
arXiv:2204.14234 [Math.AT]. https://doi.org/10.48550/ARXIV.2305.17288.
———. 2023b. “VietorisRips Complexes of Metric Spaces Near a Metric Graph.” Journal of Applied and Computational Topology, May. https://doi.org/10.1007/s41468-023-00122-z.